package com.atguigu.algorithm;

public class IslandProblem {
    /*11000
    * 11000
    * 00100
    * 00011
    * */
    public static void main(String[] args) {
        char[][] grid=new char[][]{
                {'1','1','0','0','0'},
                {'1','1','0','0','0'},
                {'0','0','1','0','0'},
                {'0','0','0','1','1'}
        };
        IslandProblem islandProblem=new IslandProblem();
        System.out.println(islandProblem.numIslands(grid));
    }
    public int numIslands(char[][] grid){
        if(grid==null || grid.length==0){
            return 0;
        }
        int res=0;
        int M=grid.length; //行数
        int N=grid[0].length; //列数
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                if(grid[i][j]=='1'){
                    res++;
                    infect(grid,i,j,M,N);
                }
            }
        }
        return res;
    }
    public void infect(char[][] grid,int i,int j,int M,int N){
        if(i>=M || j>=N || i<0 || j<0 || grid[i][j]!='1' ){
            return;
        }
        grid[i][j]='2';
        infect(grid,i+1,j,M,N);
        infect(grid,i-1,j,M,N);
        infect(grid,i,j+1,M,N);
        infect(grid,i,j-1,M,N);
    }
}
